package ali;

public class Solution_16 {


	//
	/**
	 * 思路一：递归解法
	 * 根据第一步的走法把所有走法分为两类:
	 * 第一类：第一步走了 1 个台阶
	 * 另一类：第一步走了 2 个台阶
	 *
	 * 但是会超时
	 *
	 */
	public int climbStairs(int n) {
		// 如果只有一个台阶，返回1，如果只有两个台阶，返回2
		if (n == 0 || n == 1 || n == 2) {
			return n;
		}

		// n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法 加上 先走 2 阶后，n-2 个台阶的走法
		return climbStairs(n-1) + climbStairs(n-2);

	}

	/**
	 * 思路：动态规划dp
	 * 爬第n阶楼梯的方法数量，等于2部分之和:
	 * 1、先走 1 阶后，n-1 个台阶的走法
	 * 2、先走 2 阶后，n-2 个台阶的走法
	 *
	 * 如果1个台阶：有1种走法
	 * 如果2个台阶：有2种走法
	 * 如果3个台阶：有3种走法
	 * 如果4个台阶：有5种走法
	 * 如果5个台阶：有8种走法

	 * 得到公式：dp[n] = dp[n−1] + dp[n−2]
	 * 表示，爬到第n级台阶的方案数 = 爬到第n-1级台阶的方案数 + 爬到第n-2级台阶的方案数
	 *
	 * 同时需要初始化 dp[1] = 1 和 dp[2] = 2
	 *
	 */
	public int climbStairs2(int n) {

		// 如果只有一个台阶，返回1，如果只有两个台阶，返回2
		if (n == 0 || n == 1 || n == 2) {
			return n;
		}

		int[] dp = new int[n+1];
		dp[1] = 1; // 一个台阶，有一种走法
		dp[2] = 2; // 两个台阶，有两种走法

		// n个台阶的走法
		for(int i = 3; i <= n; i++) { // 从第三步开始
			dp[i] = dp[i - 1] + dp[i - 2]; // 爬到第n级台阶的方案数 = 爬到第n-1级台阶的方案数 + 爬到第n-2级台阶的方案数
		}
		return dp[n];
	}

	public static void main(String[] args) {

		Solution_16 solution_16 = new Solution_16();
		System.out.println(solution_16.climbStairs2(5));
	}

}